package com.zhupf.binaryTree;

/**
 * @author zhupf
 * @date 2023年11月27日 11:14
 * @Description
 *
 * 543. 二叉树的直径
 */
public class DiameterOfBinaryTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,new TreeNode(2,new TreeNode(4),new TreeNode(5)),new TreeNode(3,null,null));
        DiameterOfBinaryTree diameterOfBinaryTree = new DiameterOfBinaryTree();
        System.out.println(diameterOfBinaryTree.diameterOfBinaryTree(root));
    }

    public int diameterOfBinaryTree(TreeNode root) {
        return diameter(root).sum;
    }

    public Info diameter(TreeNode root) {
        if (root == null) {
            return new Info(0,0);
        }
        Info left = diameter(root.left);
        Info right = diameter(root.right);
        int sum = left.dept + right.dept;
        left.sum = Math.max(left.sum, right.sum);
        left.dept = Math.max(left.dept, right.dept)+1;
        left.sum = Math.max(left.sum, sum);
        return left;
    }

    static class Info {

        private int dept;

        private int sum;

        public Info() {
        }
        public Info(int dept, int sum) {
            this.dept = dept;
            this.sum = sum;
        }

    }
}
